1. Field of the Invention
The present invention relates generally to data authentication, and in particular, to storing data on an untrusted machine and preserving the trustworthiness efficiently by minimizing the resource usage on a trusted computing base.
2. Background Information
Reed-Solomon (RS) was introduced by Irving S. Reed and Gustave Solomon of MIT Labs in Polynomial Codes Over Certain Finite Fields, which was published in the Journal of the Society for Industrial and Applied Mathematics in 1960. RS code is a type of Bose-Chaudhuri-Hocquenghem (hereinafter, referred to as “BCH”) code and is a linear block code. RS coding provides block error correction coding and is widely used in applications such as digital data communication and data storage. For example, RS coding has found application in such varied products as hard disk drives (HDD), CDs, DVDs, barcodes, wireless and mobile communication systems, satellite communication systems, and digital television.
The need for error correction coding arises from the inevitable data or signal noise or data errors which result whenever data is stored to a physical medium or transmitted over an imperfect communications channel. An RS encoder receives original data in a predetermined block format and adds redundant bits to the data to generate a codeword. An RS decoder receives the encoded data and related parity check data and recovers the original data when an error occurs because of transmission or storage.
RS coding of data has traditionally been performed in specially designed hardware. Attempts at software implementations have had poor performance. In the typical code, the way the hardware performs RS encoding is emulated. This means that the data is treated as bit serial and the processor manipulates the bit stream. Since it is difficult in hardware to work with less than a byte, it is usually assumed that the RS code will use Galois Field (28) (GF(28)). Because this approach does not allow for efficient processor utilization, the approach is often augmented by using special processor instructions.
With Reed-Solomon encoding of disk data for double fault tolerant disk arrays (RAID 6), each data disk in the disk array is encoded with a different element of the Galois Field. For example, data from disk 0 will be encoded with a0 and data disk n will be encoded with an. The encoded data from each disk is exclusive-or summed and placed on the parity disk. This parity is usually referred to as Q parity, while the P parity is the normal exclusive-or sum of the data disk as done for RAID 5. The combination of the 2 parities, P and Q, allows data to be recovered if any two data disks in the array should fail.
RS encoding is usually done 8 bits at a time. If D is input 8 bits of data, S is the 8 bit encoded output and V[n] represents the eight 8-bit encoding element, then the formula is illustrated as:    Bit-n of S=sum(V[n]×D), where sum=exclusive-or and multiply symbol=and. For a1, a workable V looks like:            V[0]=0 0 0 0 0 0 0 1        V[1]=1 0 0 0 0 0 0 0        V[2]=0 1 0 0 0 0 0 1        V[3]=0 0 1 0 0 0 0 1        V[4]=0 0 0 1 0 0 0 1        V[5]=0 0 0 0 1 0 0 0        V[6]=0 0 0 0 0 1 0 0        V[7]=0 0 0 0 0 0 1 0Using the above equation results with:        Bit 0 of S=bit 7 of D        Bit 1 of S=bit 0 of D        Bit 2 of S=bit 1 of D exclusive-or bit 7 of D        Bit 3 of S=bit 2 of D exclusive-or bit 7 of D        Bit 4 of S=bit 3 of D exclusive-or bit 7 of D        Bit 5 of S=bit 4 of D        Bit 6 of S=bit 5 of D        Bit 7 of S=bit 6 of D        
Hardware encoding can be realized in a large number of ways and is usually application unique. The main trade-off is the number of gates versus performance. Software encoding (and decoding) has been implemented in way that is faithful to hardware encoding. The encoding is done on successive 8 bit quantities from the input data stream. However, a large number of instructions are required to perform the necessary bit manipulation. Instead, a 256 entry table is made and every byte of data is used as an index into the table and the returned byte is the encoded value. A pseudo-code representation is illustrated as:
Read 64 bit wordIndex = result of masking off upper 7 bytesS = table(index)Store SFor next 7 bytes: Index = shift word right 8 bits Index = result of masking off upper 7 bytes Next S = table(index) Store S.
As such, for every word (8 bytes) encoded, the processor executes 32 instructions, which takes a lot more time than a HW implemented RS encoding.